<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" >

<title>每日一题20201114（1122. 数组的相对排序） | 小克的blog</title>

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="shortcut icon" href="https://woodywrx.gitee.io/blog/favicon.ico?v=1615823433634">
<link rel="stylesheet" href="https://woodywrx.gitee.io/blog/styles/main.css">



<link rel="stylesheet" href="https://unpkg.com/aos@next/dist/aos.css" />
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>



    <meta name="description" content="
重点
首先注意几个重点：

1. arr1和arr2里最大的元素不会超过1000
2. arr2里面没有重复的元素
3. arr2里面每个元素必定在arr1里面出现

思路
1. 先创建一个大小为1001的数组data用来存放arr1中每..."/>
    <meta name="keywords" content="leetcode"/>
</head>
<body>

<div id="app" class="main">

    <div class="sidebar" :class="{ 'full-height': menuVisible }">
  <div class="top-container" data-aos="fade-right">
    <div class="top-header-container">
      <a class="site-title-container" href="https://woodywrx.gitee.io/blog">
        <img src="https://woodywrx.gitee.io/blog/images/avatar.png?v=1615823433634" class="site-logo">
        <h1 class="site-title">小克的blog</h1>
      </a>
      <div class="menu-btn" @click="menuVisible = !menuVisible">
        <div class="line"></div>
      </div>
    </div>
    <div>
      
        
          <a href="https://woodywrx.gitee.io/blog" class="site-nav">
            首页
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/tags" class="site-nav">
            标签
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/post/about" class="site-nav">
            关于
          </a>
        
      
    </div>
  </div>
  <div class="bottom-container" data-aos="flip-up" data-aos-offset="0">
    <div class="social-container">
      
        
      
        
      
        
      
        
      
        
      
    </div>
    <div class="site-description">
      欢迎来到我的小窝~这里不仅有博客，也有日记。
    </div>
    <div class="site-footer">
      wuranxu's blog | <a class="rss" href="https://woodywrx.gitee.io/blog/atom.xml" target="_blank">RSS</a>
    </div>
  </div>
</div>


    <div class="main-container">
        <div class="content-container" data-aos="fade-up">
            <div class="post-detail">
                <h2 class="post-title">每日一题20201114（1122. 数组的相对排序）</h2>
                <div class="post-date">2020-11-16 15:36:35</div>
                
                <div class="post-content" v-pre>
                    <figure data-type="image" tabindex="1"><img src="https://i.loli.net/2020/11/16/gexU8aKzlYApIod.png" alt="image.png" loading="lazy"></figure>
<h4 id="重点">重点</h4>
<pre><code>首先注意几个重点：

1. arr1和arr2里最大的元素不会超过1000
2. arr2里面没有重复的元素
3. arr2里面每个元素必定在arr1里面出现
</code></pre>
<h4 id="思路">思路</h4>
<pre><code>1. 先创建一个大小为1001的数组data用来存放arr1中每个元素出现的次数（因为最大值可能是1000），其实这里可以简化，只要这个数组的长度等于max(arr1)+1即可覆盖到所有arr1中的数字；
2. 创建一个大小为arr1的数组或者直接沿用arr1（因为arr1的信息已经被记录到data数组里面了）
3. 遍历arr2，去data中取出arr1中包含arr2元素的数量，分别插入这个新数组并把data里面arr2的相关数据都置为0，保证后续data中只有arr1中特有的元素。
4. 遍历data，把剩下的数据写到新数组。
</code></pre>
<h3 id="方法一">方法一:</h3>
<pre><code class="language-Python">class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -&gt; List[int]:
        # 创建一个能容纳arr1最大值的数组
        data = [0] * (max(arr1)+1)
        # 存储arr1中的元素值和数量
        for a in arr1:
            data[a] += 1
        # 最终结果数组
        result = []
        # 把arr2的所有元素写入result数组
        for d in arr2:
            length = data[d]
            for x in range(length):
                result.append(d)
            data[d] = 0
        # i是data中剩余arr1数据的值，可能会有多个，所以需要插入n个i，当n等于0的时候代表n不存在或者n是arr2里的元素，直接continue
        for i, n in enumerate(data):
            if n == 0:
                continue
            for x in range(n):
                result.append(i)
        return result
</code></pre>
<h3 id="优化少用一个result数组直接在arr1修改">优化(少用一个result数组，直接在arr1修改)</h3>
<pre><code class="language-Python">class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -&gt; List[int]:
        data = [0] * (max(arr1)+1)
        for a in arr1:
            data[a] += 1
        # 定义一个指针指向当前已经替换的元素
        i = 0
        for d in arr2:
            length = data[d]
            for x in range(i, i+length):
                arr1[x] = d
            i += length
            data[d] = 0
        for j, n in enumerate(data):
            if n == 0:
                continue
            for x in range(i, i+n):
                arr1[x] = j
            i += n
        return arr1
</code></pre>
<figure data-type="image" tabindex="2"><img src="https://i.loli.net/2020/11/16/fYDsk2uK1oazCXi.png" alt="image.png" loading="lazy"></figure>

                </div>
                
                    <div class="tag-container">
                        
                            <a href="https://woodywrx.gitee.io/blog/vp-bY7-nD/" class="tag">
                                leetcode
                            </a>
                        
                    </div>
                

                
                    <div class="next-post">
                        <div class="next">下一篇</div>
                        <a href="https://woodywrx.gitee.io/blog/post/mei-ri-yi-ti-20201113328-qi-ou-lian-biao/">
                            <h3 class="post-title">
                                每日一题20201113（328. 奇偶链表）
                            </h3>
                        </a>
                    </div>
                
                
                    <span id="/blog/post/mei-ri-yi-ti-202011141122-shu-zu-de-xiang-dui-pai-xu/"
                          class="leancloud_visitors" data-flag-title="每日一题20201114（1122. 数组的相对排序）">
                <em class="post-meta-item-text">阅读量 </em>
                <i class="leancloud-visitors-count">0</i>
            </span>
                
                
                    

	<div id="vcomments" style="width: 100%;max-width:1000%;padding:2.5%"></div>



                

            </div>

        </div>
    </div>
</div>

<script src="https://unpkg.com/aos@next/dist/aos.js"></script>
<script type="application/javascript">

AOS.init();

var app = new Vue({
  el: '#app',
  data: {
    menuVisible: false,
  },
})

</script>






<script src='https://cdn.jsdelivr.net/npm/valine/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        appId: 'fT8wvEVNtx1cOcCQEs7rVwnV-gzGzoHsz',
        appKey: 'xV6aDHKSkLfP7u0cBRIzpmcy',
        avatar: '',
        pageSize: 5,
        recordIp: true,
        placeholder: 'Just Go Go',
        visitor: true,
    });
</script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</body>
</html>
